﻿/******************************************************************************
	Cobalt - utility libraries for building XNA games
	Copyright (C) 2008 Philip Djonov

	This program is free software; you can redistribute it and/or modify it
	under the terms of the GNU General Public License as published by the Free
	Software Foundation; either version 2 of the License, or (at your option)
	any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
	for more details.

	You should have received a copy of the GNU General Public License along
	with this program; if not, write to the
	
		Free Software Foundation, Inc.
		51 Franklin Street, Fifth Floor
		Boston, MA  02110-1301, USA.
******************************************************************************/

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Graphics.PackedVector;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;
using Microsoft.Xna.Framework.Content.Pipeline.Processors;

namespace Cobalt.Content.Pipeline.Quake.Bsp
{
	using Graphics;

	public class BspProcessor
	{
		private ContentBuildLogger logger = NullBuildLogger.NullLogger;
		public ContentBuildLogger Logger
		{
			get { return logger; }
			set { logger = value ?? NullBuildLogger.NullLogger; }
		}

		#region FlipCoordinates
		public void FlipCoordinates( ImportedBspContent content )
		{
			//entities
			foreach( var ent in content.Entities )
			{
				string orVal;
				if( ent.Values.TryGetValue( EntityKeys.Origin, out orVal ) )
				{
					Vector3 origin = EntityHelpers.ParseVec3( orVal );
					
					origin = FlipVector( origin );
					orVal = string.Format( "{0} {1} {2}", origin.X, origin.Y, origin.Z );

					ent.Values[EntityKeys.Origin] = orVal;
				}
			}

			//geometry
			FlipCoordinates( content.Mesh.Positions );
			foreach( var geom in content.Mesh.Geometry )
			{
				FlipCoordinates( (VertexChannel<Vector3>)geom.Vertices.Channels[VertexChannelNames.Normal( 0 )] );
			}

			//brushes
			foreach( var brush in content.CollisionBrushes )
			{
				foreach( var side in brush.Sides )
				{
					side.Plane = FlipPlane( side.Plane );
				}
			}

			//nodes
			foreach( var node in content.Nodes )
			{
				node.Plane = FlipPlane( node.Plane );
				node.BoundingBox = FlipBoundingBox( node.BoundingBox );
			}

			foreach( var node in content.Leaves )
			{
				node.Plane = FlipPlane( node.Plane );
				node.BoundingBox = FlipBoundingBox( node.BoundingBox );
			}
		}

		private void FlipCoordinates( IList<Vector3> coords )
		{
			for( int i = 0; i < coords.Count; i++ )
			{
				coords[i] = FlipVector( coords[i] );
			}
		}

		public static Vector3 FlipVector( Vector3 v )
		{
			return new Vector3( -v.X, v.Z, v.Y );
		}

		public static Plane FlipPlane( Plane p )
		{
			return new Plane( FlipVector( p.Normal ), p.D );
		}

		public static BoundingBox FlipBoundingBox( BoundingBox box )
		{
			Vector3 mins = FlipVector( box.Min );
			Vector3 maxs = FlipVector( box.Max );

			return new BoundingBox( Vector3.Min( mins, maxs ),
				Vector3.Max( mins, maxs ) );
		}
		#endregion

		#region CombineLightmaps
		public void CombineLightmaps( ImportedBspContent content, int maxLightmapSize, bool allowNpo2Lightmaps )
		{
			if( content.Lightmaps.Count > 0 &&
				(content.Lightmaps[0].Mipmaps[0].Width > maxLightmapSize ||
				content.Lightmaps[0].Mipmaps[0].Height > maxLightmapSize) )
				return;

			int numTargets = 0;
			var placements = new Dictionary<Texture2DContent, LightmapPlacement>();

			int placementX = 0;
			int placementY = 0;
			int maxY = 0;

			foreach( var inImg in content.Lightmaps )
			{
				int w = inImg.Mipmaps[0].Width;
				int h = inImg.Mipmaps[0].Height;

				if( placementX + w > maxLightmapSize )
				{
					//row is full, will have to start another...

					if( maxY + h > maxLightmapSize )
					{
						//...on a new target
						numTargets++;
						placementY = 0;
					}
					else
					{
						placementY = maxY;
					}

					placementX = 0;
					maxY = placementY + h;
				}

				placements.Add( inImg, new LightmapPlacement()
				{
					TargetIndex = numTargets,
					TargetRectangle = new Rectangle( placementX, placementY, w, h ),
				} );

				maxY = Math.Max( maxY, placementY + h );
				placementX += w;
			}

			var targets = new List<LightmapTarget>( numTargets + 1 );
			for( int i = 0; i <= numTargets; i++ )
				targets.Add( null );

			foreach( var placement in placements )
			{
				var target = targets[placement.Value.TargetIndex];
				if( target == null )
				{
					target = new LightmapTarget( maxLightmapSize, allowNpo2Lightmaps );
					targets[placement.Value.TargetIndex] = target;
				}

				target.AddImage( placement.Key, placement.Value.TargetRectangle );
			}

			var newLmaps = new List<Texture2DContent>();
			var lmapRemap = new Dictionary<Texture2DContent, Texture2DContent>();


			foreach( var lmap in content.Lightmaps )
			{
				if( placements.ContainsKey( lmap ) )
					continue;

				newLmaps.Add( lmap );
				lmapRemap.Add( lmap, lmap );
			}

			foreach( var target in targets )
			{
				if( target == null || target.Image.Mipmaps.Count == 0 )
					continue;

				newLmaps.Add( target.Image );
			}

			foreach( var placement in placements )
			{
				var target = targets[placement.Value.TargetIndex];

				AdjustLightmapReferences( content, placement.Key,
					new Rectangle( 0, 0, target.MaxX, target.MaxY ),
					placement.Value.TargetRectangle );

				lmapRemap.Add( placement.Key, target.Image );
			}

			Logger.LogMessage( "Stitched {0} lightmaps down to {1}.", content.Lightmaps.Count, newLmaps.Count );

			content.Lightmaps.Clear();
			content.Lightmaps.AddRange( newLmaps );

			foreach( var mat in content.Materials )
			{
				Texture2DContent newLmap;
				if( mat.Lightmap != null && lmapRemap.TryGetValue( mat.Lightmap, out newLmap ) )
					mat.Lightmap = newLmap;
			}
		}

		private struct LightmapPlacement
		{
			public int TargetIndex;
			public Rectangle TargetRectangle;
		}

		private class LightmapTarget
		{
			private bool allowNpo2;
			private int maxSize;

			public Texture2DContent Image;
			public int MaxX, MaxY;

			public LightmapTarget( int maxSize, bool allowNpo2 )
			{
				Image = new Texture2DContent();

				this.maxSize = maxSize;
				this.allowNpo2 = allowNpo2;
			}

			private void Grow( int w, int h )
			{
				if( !allowNpo2 )
				{
					w = Helpers.RoundUpToPowerOf2( w );
					h = Helpers.RoundUpToPowerOf2( h );
				}

				w = Math.Max( w, MaxX );
				h = Math.Max( h, MaxY );

				if( Image.Mipmaps.Count == 0 )
				{
					Image.Mipmaps.Add( new PixelBitmapContent<Color>( w, h ) );

					MaxX = w;
					MaxY = h;

					return;
				}

				var dest = new PixelBitmapContent<Color>( w, h );
				BitmapContent.Copy( Image.Mipmaps[0], new Rectangle( 0, 0, MaxX, MaxY ),
					dest, new Rectangle( 0, 0, MaxX, MaxY ) );

				Image.Mipmaps[0] = dest;

				MaxX = w;
				MaxY = h;
			}

			public void AddImage( Texture2DContent image, Rectangle rc )
			{
				if( rc.Right > MaxX || rc.Bottom > MaxY )
					Grow( rc.Right, rc.Bottom );

				BitmapContent.Copy( image.Mipmaps[0], new Rectangle( 0, 0, rc.Width, rc.Height ),
					this.Image.Mipmaps[0], rc );
			}
		}

		private void AdjustLightmapReferences( ImportedBspContent content, Texture2DContent lmap, Rectangle imageRect, Rectangle subRect )
		{
			float xs = (float)subRect.Width / (float)imageRect.Width;
			float ys = (float)subRect.Height / (float)imageRect.Height;

			float xb = (float)(subRect.Left - imageRect.Left) / (float)imageRect.Width;
			float yb = (float)(subRect.Top - imageRect.Top) / (float)imageRect.Height;

			foreach( GeometryContent gc in content.Mesh.Geometry )
			{
				var mat = gc.Material as ImportedMaterialContent;
				if( mat.Lightmap != lmap )
					continue;

				VertexChannel<Vector2> lmapUvs = (VertexChannel<Vector2>)
					gc.Vertices.Channels[VertexChannelNames.TextureCoordinate( 1 )];

				for( int i = 0; i < lmapUvs.Count; i++ )
				{
					Vector2 v = lmapUvs[i];
					lmapUvs[i] = new Vector2( v.X * xs + xb, v.Y * ys + yb );
				}
			}
		}
		#endregion

		#region CollapseDuplicateMaterials
		public void CollapseDuplicateMaterials( ImportedBspContent content )
		{
			var matMap = new Dictionary<ImportedMaterialContent, ImportedMaterialContent>();

			int matsRemoved = 0;
			for( int i = 0; i < content.Materials.Count; i++ )
			{
				var matI = content.Materials[i];
				matMap.Add( matI, matI );

				for( int j = i + 1; j < content.Materials.Count; j++ )
				{
					var matJ = content.Materials[j];

					if( matI.Shader != matJ.Shader || matI.Lightmap != matJ.Lightmap )
						continue;

					content.Materials.RemoveAt( j-- );
					matMap.Add( matJ, matI );

					matsRemoved++;
				}
			}

			Logger.LogMessage( "Removed {0} redundant materials.", matsRemoved );

			foreach( var gc in content.Mesh.Geometry )
			{
				gc.Material = matMap[(ImportedMaterialContent)gc.Material];
			}
		}
		#endregion

		#region ReformatLightmaps
		public void ReformatLightmaps( ImportedBspContent content )
		{
			var lmapRemap = new Dictionary<Texture2DContent, Texture2DContent>();

			for( int i = 0; i < content.Lightmaps.Count; i++ )
			{
				Texture2DContent inImg = content.Lightmaps[i];

				Texture2DContent newImg = new Texture2DContent();

				foreach( BitmapContent inBmp in inImg.Mipmaps )
				{
					var newBmp = new PixelBitmapContent<Bgr565>( inBmp.Width, inBmp.Height );

					if( content.RescaleLightmaps )
					{
						var inPixels = (PixelBitmapContent<Color>)inBmp;

						for( int y = 0; y < newBmp.Height; y++ )
						{
							for( int x = 0; x < newBmp.Width; x++ )
							{
								Color inPix = inPixels.GetPixel( x, y );

								byte r = inPix.R;
								byte g = inPix.G;
								byte b = inPix.B;

								ScaleQuakeLighting( ref r, ref g, ref b );

								Bgr565 outPix = new Bgr565(
									Helpers.ExpandByte( r ),
									Helpers.ExpandByte( g ),
									Helpers.ExpandByte( b ) );

								newBmp.SetPixel( x, y, outPix );
							}
						}
					}
					else
					{
						BitmapContent.Copy( inBmp, newBmp );
					}

					newImg.Mipmaps.Add( newBmp );
				}

				newImg.GenerateMipmaps( false );

				content.Lightmaps[i] = newImg;
				lmapRemap.Add( inImg, newImg );
			}

			foreach( var mat in content.Materials )
			{
				Texture2DContent newLmap;
				if( mat.Lightmap != null && lmapRemap.TryGetValue( mat.Lightmap, out newLmap ) )
					mat.Lightmap = newLmap;
			}
		}

		public static void ScaleQuakeLighting( ref byte rb, ref byte gb, ref byte bb )
		{
			int r = rb << 2;
			int g = gb << 2;
			int b = bb << 2;

			if( (r | g | b) > 0xFF )
			{
				int max = Helpers.Max( r, g, b );

				r = (r * 0xFF) / max;
				g = (g * 0xFF) / max;
				b = (b * 0xFF) / max;
			}

			rb = (byte)r;
			gb = (byte)g;
			bb = (byte)b;
		}
		#endregion

		#region RescaleVertexLighting
		public void RescaleVertexLighting( ImportedBspContent content )
		{
			foreach( GeometryContent gc in content.Mesh.Geometry )
			{
				VertexChannel<Color> colorChan = (VertexChannel<Color>)gc.Vertices.Channels[VertexChannelNames.Color( 0 )];
				if( colorChan == null )
					continue;

				for( int i = 0; i < colorChan.Count; i++ )
				{
					Color cl = colorChan[i];

					byte r = cl.R;
					byte g = cl.G;
					byte b = cl.B;

					ScaleQuakeLighting( ref r, ref g, ref b );

					colorChan[i] = new Color( r, g, b, cl.A );
				}
			}
		}
		#endregion

		#region CompileEntities
		public List<Entity> CompileEntities( ImportedBspContent content )
		{
			var ret = new List<Entity>();

			foreach( ImportedEntityContent srcEnt in content.Entities )
			{
				Entity ent;
				switch( srcEnt.ClassName )
				{
					case EntityClasses.WorldSpawn:
						ent = new WorldSpawnEntity();
						break;

					case EntityClasses.Light:
						ent = new LightEntity();
						break;

					default:
						ent = new Entity();
						break;
				}

				try
				{
					ent.Initialize( srcEnt.Values );
				}
				catch( Exception ex )
				{
					throw new InvalidContentException( "Failed entity compilation.",
						srcEnt.Identity, ex );
				}

				ret.Add( ent );
			}

			foreach( Entity ent in ret )
			{
				string targetName;
				if( ent.MiscValues.TryGetValue( EntityKeys.Target, out targetName ) )
				{
					Entity target = ret.Find( e => e.MiscValues.ValueEquals( EntityKeys.TargetName, targetName ) );

					ent.Target = target;
					ent.MiscValues.Remove( EntityKeys.Target );
				}
			}

			return ret;
		}
		#endregion

		#region SimplifyPvs
		public void SimplifyPvs( ImportedBspContent content, int targetClusterSize )
		{
			//map removed clusters to the ones they get merged in with
			var pvsMap = new Dictionary<PvsCluster, PvsCluster>();
			//grab a list of all the clusters
			List<PvsCluster> clusters = content.PvsData.Clusters;

			//get a count of all the geometry in them
			var geometryCounts = new List<int>( clusters.Count );
			for( int i = 0; i < clusters.Count; i++ )
				geometryCounts.Add( 0 );

			foreach( var node in content.Leaves )
			{
				if( node.Cluster == null )
					continue;

				foreach( GeometryContent geom in node.Surfaces )
					geometryCounts[node.Cluster.ClusterNum] += geom.Indices.Count;
			}

			var clusterJointness = ComputeClusterJointness( content );

			int clustersRemoved = 0;

			for( ; ; )
			{
				//starting with the smallest cluster...
				clusters.Sort( ( a, b ) => geometryCounts[a.ClusterNum] - geometryCounts[b.ClusterNum] );

				bool didMerge = false;
				foreach( var clus in clusters )
				{
					//skip it if it has been merged away...
					if( pvsMap.ContainsKey( clus ) )
						continue;

					int clusCount = geometryCounts[clus.ClusterNum];

					//or is already large enough...
					if( clusCount >= targetClusterSize * 3 )
						continue;

					List<PvsCluster> links = new List<PvsCluster>( clus.Links );

					//or connects to nothing...
					if( links.Count == 0 )
						continue;

					//If we have reached this point, we essentially have a small cluster
					//that we'd like to grow. We grow the cluster by having it absorb the
					//clusters it is linked to...

					//...starting with the largest jointest
					links.Sort( ( a, b ) => clusterJointness[new Helpers.Pair<PvsCluster, PvsCluster>( clus, a )] -
						clusterJointness[new Helpers.Pair<PvsCluster, PvsCluster>( clus, b )] );

					foreach( var link in links )
					{
						//unless the linked cluster has been collapsed to some other place
						if( pvsMap.ContainsKey( link ) )
							continue;

						//or is not linked both ways
						if( !link.CanSee( clus ) )
							continue;

						//or would make this one too big if merged
						int linkCount = geometryCounts[link.ClusterNum];
						if( linkCount > 64 * 3 && clusCount + linkCount > targetClusterSize * 5 )
							continue;

						//At this point we know we want to combine link into clus.
						//Let the merging begin!

						//first off, link is about to die, so it should not be pointed to by clus
						clus.BreakLink( link );

						//anything else that points to it should be redirected to clus
						foreach( var otherClus in clusters )
						{
							if( otherClus.CanSee( link ) )
							{
								otherClus.BreakLink( link );
								otherClus.AddLink( clus );
							}
						}

						//and anything it points to, clus needs to point to as well
						foreach( var linkLink in link.Links )
							clus.AddLink( linkLink );

						//note that everything that pointed to link is now clus
						pvsMap[link] = clus;

						//account for merged geometry
						clusCount += geometryCounts[link.ClusterNum];
						geometryCounts[link.ClusterNum] = 0;

						//note that there was a merge (and that another pass may be necessary)
						didMerge = true;
						clustersRemoved++;
					}

					geometryCounts[clus.ClusterNum] = clusCount;
				}

				if( !didMerge )
					//if we got through everything without merging, we're done
					break;
			}

			pvsMap = pvsMap.CollapseChainMappings();

			//remove anything that was mapped away
			foreach( PvsCluster clus in pvsMap.Keys )
				clusters.Remove( clus );

			//renumber the clusters
			for( int i = 0; i < clusters.Count; i++ )
				clusters[i].ClusterNum = i;

			//remap the pointers off the leaves
			foreach( var node in content.Leaves )
			{
				if( node.Cluster == null )
					continue;

				PvsCluster t, v = node.Cluster;
				if( pvsMap.TryGetValue( v, out t ) )
					node.Cluster = t;
			}

			Logger.LogMessage( "Merged away {0} PVS clusters.", clustersRemoved );
		}

		private int ComputeSurfaceJointness( GeometryContent surfA, GeometryContent surfB )
		{
			int ret = 0;

			foreach( int pA in surfA.Vertices.PositionIndices )
			{
				foreach( int pB in surfB.Vertices.PositionIndices )
				{
					if( pA == pB )
					{
						ret++;
						break;
					}
				}
			}

			return ret;
		}

		private int ComputeSurfaceJointness( List<GeometryContent> listA, List<GeometryContent> listB, Dictionary<GeometryContent, BoundingBox> surfaceBounds )
		{
			int ret = 0;

			foreach( GeometryContent surfA in listA )
			{
				BoundingBox bbA = surfaceBounds[surfA];

				foreach( GeometryContent surfB in listB )
				{
					if( !bbA.Intersects( surfaceBounds[surfB] ) )
						continue;

					ret += ComputeSurfaceJointness( surfA, surfB );

					if( surfA.Material == surfB.Material )
						ret += (surfA.Indices.Count + surfB.Indices.Count) / (4 * 3);
				}
			}

			return ret;
		}

		private Dictionary<Helpers.Pair<PvsCluster, PvsCluster>, int> ComputeClusterJointness( ImportedBspContent content )
		{
			var surfaceBounds = new Dictionary<GeometryContent, BoundingBox>();
			foreach( var gc in content.Mesh.Geometry )
			{
				surfaceBounds.Add( gc, BoundingBox.CreateFromPoints( gc.Vertices.Positions ) );
			}

			var clusterSurfaces = new Dictionary<PvsCluster, List<GeometryContent>>();

			foreach( var cluster in content.PvsData.Clusters )
				clusterSurfaces.Add( cluster, new List<GeometryContent>() );

			foreach( var leaf in content.Leaves )
			{
				if( leaf.Cluster == null )
					continue;

				clusterSurfaces[leaf.Cluster].AddRange( leaf.Surfaces );
			}

			var ret = new Dictionary<Helpers.Pair<PvsCluster, PvsCluster>, int>();

			foreach( var clusA in content.PvsData.Clusters )
			{
				var surfsA = clusterSurfaces[clusA];

				foreach( var clusB in content.PvsData.Clusters )
				{
					if( clusA == clusB )
					{
						//doesn't get any jointer
						ret.Add( new Helpers.Pair<PvsCluster, PvsCluster>( clusA, clusB ), int.MaxValue );
						continue;
					}

					int jointness = clusA.CanSee( clusB ) ? ComputeSurfaceJointness( surfsA, clusterSurfaces[clusB], surfaceBounds ) : 0;
					ret.Add( new Helpers.Pair<PvsCluster, PvsCluster>( clusA, clusB ), jointness );
				}
			}

			return ret;
		}
		#endregion

		#region MergeSurfaces and RemoveEmptySurfaces
		public void MergeSurfaces( ImportedBspContent content, IEnumerable<IEnumerable<GeometryContent>> mergeGroups )
		{
			int numMerges;
			Dictionary<GeometryContent, GeometryContent> geoRemap;
			MeshHelpers.MergeGeometries( content.Mesh, mergeGroups, ushort.MaxValue, int.MaxValue,
				out geoRemap, out numMerges );

			RemapGeometryReferences( content, geoRemap );

			if( numMerges > 0 )
				Logger.LogMessage( "Merged away {0} surfaces.", numMerges );
		}

		public void RemoveEmptySurfaces( ImportedBspContent content )
		{
			int numRem = 0;

			Dictionary<GeometryContent, GeometryContent> geoRemap = new Dictionary<GeometryContent, GeometryContent>();
			for( int i = content.Mesh.Geometry.Count; i-- != 0; )
			{
				GeometryContent gc = content.Mesh.Geometry[i];

				if( gc.Vertices.VertexCount == 0 ||
					gc.Indices.Count == 0 )
				{
					numRem++;
					geoRemap.Add( gc, null );
					content.Mesh.Geometry.RemoveAt( i );
				}
				else
				{
					geoRemap.Add( gc, gc );
				}
			}

			RemapGeometryReferences( content, geoRemap );

			if( numRem > 0 )
				Logger.LogMessage( "Removed {0} empty surfaces.", numRem );
		}

		private void RemapGeometryReferences( ImportedBspContent content, Dictionary<GeometryContent, GeometryContent> geoRemap )
		{
			foreach( ImportedBrushModelContent brush in content.BrushModels )
			{
				Helpers.Remap( brush.Surfaces, geoRemap );
				Helpers.RemoveNullEntries( brush.Surfaces );
				Helpers.RemoveDuplicateEntries( brush.Surfaces );
			}

			foreach( var node in content.Leaves )
			{
				node.Surfaces.Remap( geoRemap );
				node.Surfaces.RemoveNullEntries();
				node.Surfaces.RemoveDuplicateEntries();
			}
		}
		#endregion

		#region GetMergeGroups
		public IEnumerable<IEnumerable<GeometryContent>> GetMergeGroups( ImportedBspContent content )
		{
			List<List<GeometryContent>> meshGroups = GetMeshGroups( content );

			Dictionary<GeometryContent, List<int>> meshUsers = new Dictionary<GeometryContent, List<int>>();

			for( int i = 0; i < meshGroups.Count; i++ )
			{
				foreach( GeometryContent gc in meshGroups[i] )
				{
					List<int> bucket;
					if( !meshUsers.TryGetValue( gc, out bucket ) )
					{
						bucket = new List<int>();
						meshUsers.Add( gc, bucket );
					}

					bucket.Add( i );
				}
			}

			List<KeyValuePair<GeometryContent, List<int>>> users = new List<KeyValuePair<GeometryContent, List<int>>>( meshUsers );

			var ret = new List<IEnumerable<GeometryContent>>();

			for( int i = 0; i < users.Count; i++ )
			{
				List<GeometryContent> mergeGroup = new List<GeometryContent>();
				mergeGroup.Add( users[i].Key );

				for( int j = i + 1; j < users.Count; j++ )
				{
					if( Helpers.ListsEqual( users[j].Value, users[i].Value ) )
					{
						mergeGroup.Add( users[j].Key );
						users.RemoveAt( j-- );
					}
				}

				ret.Add( mergeGroup );
			}

			return ret;
		}

		private List<List<GeometryContent>> GetMeshGroups( ImportedBspContent content )
		{
			List<List<GeometryContent>> ret = new List<List<GeometryContent>>();

			foreach( ImportedBrushModelContent bmodel in content.BrushModels )
			{
				ret.Add( new List<GeometryContent>( bmodel.Surfaces ) );
			}

			var leaves = new List<ImportedNodeContent>( content.Leaves );

			for( int i = 0; i < leaves.Count; i++ )
			{
				var leaf = leaves[i];
				var bucket = new List<GeometryContent>();

				bucket.AddRange( leaf.Surfaces );

				for( int j = i + 1; j < leaves.Count; j++ )
				{
					if( leaves[j].Cluster == leaf.Cluster )
					{
						bucket.AddRange( leaves[j].Surfaces );
						leaves.RemoveAt( j-- );
					}
				}

				bucket.RemoveDuplicateEntries();

				ret.Add( bucket );
			}

			//split by material

			for( int i = 0; i < ret.Count; i++ )
			{
				List<GeometryContent> bucket = ret[i];

				if( bucket.Count == 0 )
				{
					ret.RemoveAt( i-- );
					continue;
				}

				Dictionary<MaterialContent, List<GeometryContent>> newBuckets = new Dictionary<MaterialContent, List<GeometryContent>>();

				for( int j = bucket.Count - 1; j >= 1; j-- )
				{
					if( bucket[j].Material == bucket[0].Material )
						continue;

					List<GeometryContent> destBucket;
					if( !newBuckets.TryGetValue( bucket[j].Material, out destBucket ) )
					{
						destBucket = new List<GeometryContent>();
						newBuckets.Add( bucket[j].Material, destBucket );
					}

					destBucket.Add( bucket[j] );
					bucket.RemoveAt( j );
				}

				ret.AddRange( newBuckets.Values );

			}

			return ret;
		}
		#endregion
	}

}